package com.programmercarl.greed;

import java.util.Arrays;
import java.util.Comparator;

/**
 * https://leetcode.cn/problems/non-overlapping-intervals/description/
 * 无重叠区间    AC
 *
 * @author yulongtian
 * @create 2025-02-07 15:18
 */
public class Test12 {
    public static void main(String[] args) {
        Test12 test12 = new Test12();
        int[][] intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
        System.out.println(test12.eraseOverlapIntervals(intervals));
        System.out.println(Arrays.deepToString(intervals));
    }

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });
        int count = 0;
        for (int i = 1; i < intervals.length; i++) {
            // 无重叠
            if (intervals[i][0] >= intervals[i - 1][1]) {
                continue;
            }
            // 有重叠
            intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
            count++;
        }

        return count;
    }

}
